package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/*
https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

235. 二叉搜索树的最近公共祖先

示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

 */
class leetcode_235 {
    @Test
    fun test_1() {
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val n8 = TreeNode(8)
        val n9 = TreeNode(9)
        val root: TreeNode = n6
        root.left = n2
        root.right = n8
        n2.left = n0
        n2.right = n4
        n4.left = n3
        n4.right = n5
        n8.left = n7
        n8.right = n9
        val actual = lowestCommonAncestor(root, n2, n8)
        val expect = n6
        Assert.assertTrue(actual == expect)
    }

    @Test
    fun test_2() {
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val n8 = TreeNode(8)
        val n9 = TreeNode(9)
        val root: TreeNode = n6
        root.left = n2
        root.right = n8
        n2.left = n0
        n2.right = n4
        n4.left = n3
        n4.right = n5
        n8.left = n7
        n8.right = n9
        val actual = lowestCommonAncestor(root, n2, n3)
        val expect = n2
        Assert.assertTrue(actual == expect)
    }

    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        /*
        因为二叉搜索树自带顺序，所以不用考虑使用哪种遍历方式。
        只要root 在 p 和 q 中间，那么root 就是p 和 q 的最近公共祖先。
        不用考虑p 和 q 谁更大
         */
        //  return lowestCommonAncestor1(root,p,q)
        return lowestCommonAncestor2(root, p, q)
    }

    fun lowestCommonAncestor1(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        // 递归
        // T - LogN
        // S - H

        // 终止条件
        if (null == root || null == p || null == q) {
            return null
        }

        // 左
        if (root.`val` > p.`val` && root.`val` > q.`val`) {
            val left: TreeNode? = lowestCommonAncestor1(root.left, p, q)
            if (left != null) {
                return left
            }
        }

        // 右
        if (root.`val` < p.`val` && root.`val` < q.`val`) {
            val right: TreeNode? = lowestCommonAncestor1(root.right, p, q)
            if (null != right) {
                return right
            }
        }

        // 说明 root value 在 p 和 q 中间，那么找到了这个节点
        return root
    }

    fun lowestCommonAncestor2(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        // 迭代法
        // T - N
        // S - H
        if (null == root || null == p || null === q) {
            return null
        }

        var current: TreeNode? = root
        while (current != null) {
            if (current.`val` > p.`val` && current.`val` > q.`val`) {
                // 在右边
                current = current.left
            } else if (current.`val` < p.`val` && current.`val` < q.`val`) {
                // 在左边
                current = current.right
            } else { // 说明 current value 在 p 和 q 中间，那么找到了这个节点
                // 在中间
                return current
            }
        }
        return null
    }
}